#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <errno.h>

/* Constants */
#define MAXLINE    1024   /* max line size :                 pow(2,10)  */
#define MAXARGS     128   /* max args on a command line :    pow(2,7)   */
#define MAXJOBS    1024   /* max jobs at any point in time : pow(2,10)  */
#define MAXPATH      64   /* max length of path :            pow(2,6)   */

/* Job states */
#define UNDEF 0 /* undefined */
#define FG 1    /* running in foreground */
#define BG 2    /* running in background */
#define ST 3    /* stopped */

/* 
 * Jobs states: FG (foreground), BG (background), ST (stopped)
 * Job state transitions and enabling actions:
 *     FG -> ST  : ctrl-z
 *     ST -> FG  : fg command
 *     ST -> BG  : bg command
 *     BG -> FG  : fg command
 * At most 1 job can be in the FG state.
 */


/* Global variables */
extern char **environ;      /* defined in libc */
char prompt[MAXLINE];      /* command line prompt (DO NOT CHANGE) */
char sbuf[MAXLINE];         /* for composing sprintf messages */
char userPath[]="/home/betaberry";
// char userPath[]="/home/wyz";


// history recorder
int his_next_index=0;
char his[MAXLINE][MAXJOBS];


//job
typedef struct job_t job_t;
struct job_t {     
    pid_t pid;              /* job PID */
    int state;              /* UNDEF, BG, FG, or ST */
    char cmdline[MAXLINE];  /* command line */
};

int next_job_index = 0;
int fg_job_num = 0;
struct job_t jobs[MAXJOBS];  /* The job list */
/* End global variables */






/* Function prototypes */
void eval(char *cmdline);
void parseline(const char *cmdline, char **argv, int *res, int *line, int* pipe_num); 
int builtin_cmd(char **argv);
void do_bgfg(char **argv);
void waitfg_1(pid_t pid);
void waitfg_2();

void sigchld_handler(int sig);
void sigtstp_handler(int sig);
void sigint_handler(int sig);
void sigquit_handler(int sig);



void clearJob(struct job_t *job);
void initJobs();
int addJob(struct job_t *jobs, pid_t pid, int state, char *cmdline);
int deleteJob(struct job_t *jobs, pid_t pid);
void listjobs(struct job_t *jobs);
pid_t fgPID(struct job_t *jobs);
struct job_t *getJobByPID(struct job_t *jobs, pid_t pid);
struct job_t *getJobByJID(struct job_t *jobs, int jid); 
int pid2jid(pid_t pid); 
int jid2pid(int jid);



void initHis();
int history1(struct job_t *jobs);
int history2(struct job_t *jobs,int n);

void usage(void);
void unix_error(char *msg);
void app_error(char *msg);
typedef void handler_t(int);
handler_t *Signal(int signum, handler_t *handler);



/*
 * main - The shell's main routine 
 */
int main(int argc, char **argv) 
{
	getcwd(prompt,MAXPATH);
	strcat(prompt," $");

    char cmdline[MAXLINE];

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1,2);

    /* Parse the command line */

    /* Install the signal handlers */
    Signal(SIGINT,  sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    signal(SIGQUIT, sigquit_handler); 

    /* Initialize the job list */
    initJobs();

    /* Initialize the history list */
    initHis();

    /* Execute the shell's read/eval loop */
    while (1)
    {
		/* Read command line */
	    printf("%s", prompt);
	    fflush(stdout);

		
		if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
		    app_error("fgets error");
		
		if (feof(stdin))    /* End of file (ctrl-d) */
		{
		    fflush(stdout);
		    exit(0);
		}

		/*record every instrument*/
		if(strlen(cmdline)>1)
		{
			strcpy(his[his_next_index],cmdline);
			++his_next_index;
		}


		/* Evaluate the command line */
		eval(cmdline);
	

		fflush(stdout);
		fflush(stdout);
    } 
    exit(0); /* control never reaches here */
}






/* 
 * eval - Evaluate the command line that the user has just typed in
 * 
 * If it is a built-in command
 * if it is an another program
 *
 */
void eval(char *cmdline)
{

/*    
 *   error                  res[0]
 *	 bg '&'                 res[1]
 *   location of '<'        res[2]
 *   location of '>'        res[3]
 *   location of '>>'       res[4]
 */

	char buf[MAXLINE];   /* Holds modified command line */
	char *argv[MAXARGS]; /* Argument list execve() */



	/* the note table */
	int res[5];
	for(int i = 0; i < 5; ++i)
		res[i] = 0; //attention here



	/* the number of '|', namely the number of pipe */
	int pipe_num = 0;
	int* p = &pipe_num;



	/* each '|''s start location, suppose there was a '|' in the very beginning */
	int line[MAXPATH];  
	for(int i = 0; i < MAXPATH; ++i)
		line[i] = -2;  //attention here, because we need to place -1 in line[0], so we have to use -2 to initialize
	line[0] = -1;      //the first process is in the 0's place, so we use -1 to begin


	strcpy(buf, cmdline);
	parseline(buf, argv, res, line, p);     /*argv is settled*/


	/* ignore the wrong instrument */
	if (res[0] == 1)
		return;                    

	
	if (!builtin_cmd(argv))         /* check if it is a built_in cmd*/
	{
		sigset_t blockset;
		sigemptyset(&blockset);
		sigaddset(&blockset, SIGCHLD);
		sigprocmask(SIG_BLOCK, &blockset, NULL);


		/*for n pipe, we need n+1 subprocess, we need n+1 pid*/
		pid_t pid[pipe_num+1];
		for(int i = 0; i <= pipe_num; ++i)
			pid[i] = -1;


		/* create n pipes */
		int fd[pipe_num][2];  
		for(int i = 0; i < pipe_num; ++i)
			pipe(fd[i]);


		/* create n+1 processes, */
		for(int i=0; i<=pipe_num; ++i)
		{
			if(i==0)
			{
				pid[i] = fork();
			}

			else if(pid[i-1]>0)
				pid[i] = fork();

		}

		/* locate to the i'th job */
		for(int i=0; i<=pipe_num; ++i)
		{
			if (pid[i] == 0)     
			{

				int file_in;
				int file_out;
				int file_continue_out;


				/* deal with pipe */
				if(pipe_num)
					if(i==0)
					{
						close(1);
						close(fd[0][0]);
						dup(fd[0][1]);
						close(fd[0][1]);
					}

					else if(i==pipe_num)
					{
						close(0);
						close(fd[i-1][1]);
						dup(fd[i-1][0]);
						close(fd[i-1][0]);
					}

					else
					{
						close(0);
						close(fd[i-1][1]);
						dup(fd[i-1][0]);
						close(fd[i-1][0]);

						close(1);
						close(fd[i][0]);
						dup(fd[i][1]);
						close(fd[i][0]);
					}


				/* deal with redirect */
				if(1)
				{
					if(i == 0)
						if(res[2])
						{
							
							file_in=open(argv[res[2]+1],O_RDONLY);

							if(!file_in)
							{
								printf("%s: No such file or directory",argv[res[2]+1]);
								exit(0);
							}

							close(0);
							dup(file_in);
						}

					if(i == pipe_num)
					{
						if(res[3])
						{
							
							file_out = open(argv[res[3]+1],O_WRONLY);

							if(!file_out)
							{
								printf("%s: No such file or directory",argv[res[3]+1]);
								exit(0);
							}

							close(1);
							dup(file_out);
						}

						if(res[4])
						{
							file_continue_out=open(argv[res[4]+1],O_WRONLY | O_APPEND);

							if(!file_continue_out)
							{
								printf("%s: No such file or directory",argv[res[2]+1]);
								exit(0);
							}

							close(1);
							dup(file_continue_out);
						}
					}
				}


				/* carry out each process */
				if(execve(argv[line[i]+1],argv+line[i]+1,environ)<0)    /* First think if the instrument is local */
				{
					if(execvp(argv[line[i]+1],argv+line[i]+1)<0)      /* Second think if the instrument is in /bin */ 
					{   
						printf("%s: Command not found.\n", argv[0]);
						exit(0);
					}

				}

			}

		}

		/* father duty */

		//close all the pipe
		for(int i=0; i < pipe_num; ++i)
		{
			close(fd[i][0]);
			close(fd[i][1]);
		}

		if (!res[1])    //foreground job
		{
			fg_job_num = pipe_num+1;
			for(int j=0;j<=pipe_num;++j)
			{
				addJob(jobs, pid[j], FG, cmdline);
				sigprocmask(SIG_UNBLOCK, &blockset, NULL);

			}

			for(int j=0; j<=pipe_num; ++j)
			{
				waitfg_2();
				waitpid(pid[j],NULL,0);
			}

		}

		else if(res[1])    //backgroud job
		{
			for(int j=0; j<=pipe_num; ++j)
			{
				addJob(jobs, pid[j], BG, cmdline);
				// sigprocmask(SIG_UNBLOCK, &blockset, NULL);
				printf("[%d] %s", pid[j], cmdline);
			}

	    }

    }

    return;
}



/* 
 * parseline - Parse the command line and build the argv array.
 * 
 * return the number of pipes in need
 *  
 *   error                  res[0]
 *	 bg '&'                 res[1]
 *   location of '<'        res[2]
 *   location of '>'        res[3]
 *   location of '>>'       res[4]
 */
void parseline(const char *cmdline, char **argv, int *res, int* line, int* pipe_num) 
{
    static char array[MAXLINE]; /* holds local copy of command line */


    char *buf = array;          /* ptr that traverses command line */
    char *delim;                /* points to first space delimiter */
    int argc;                   /* number of args */
    int line_index;             /* number of '|' */


    strcpy(buf, cmdline);
    buf[strlen(buf)-1] = ' ';  /* replace trailing '\n' with space */
    
    while (*buf && (*buf == ' ')) /* ignore leading spaces */
		buf++;

    /* Build the argv list */
    if (*buf == '\'')
    {
		buf++;
		delim = strchr(buf, '\'');
    }

    else 
    {
		delim = strchr(buf, ' ');
    }

    argc=0;
    line_index=1;
    while (delim) 
    {
		*delim = '\0';

		if(!strcmp(buf, "|"))
		{
			line[line_index]=argc;
			if(argc == 0)
			{
				printf("you can't begin with '|'\n");
				res[0]=1;
				return;
			}
			argv[argc] = NULL;
			++line_index;
		}

		else if(!strcmp(buf,"<"))
		{
			if(res[2])
			{
				printf("too many `<'\n");
				res[0]=1;
				return;
			}
			res[2]=argc;
			argv[argc] = NULL;
		}

		else if(!strcmp(buf,">")) 
		{
			if(res[3])
			{
				printf("too many `>'\n");
				res[0]=1;
				return;
			}

			res[3]=argc;
			argv[argc] = NULL;
		}

		else if(!strcmp(buf,">>")) 
		{
			if(res[4])
			{
				res[0]=1;
				printf("too many `>'\n");
				return;
			}

			res[4]=argc;
			argv[argc] = NULL;

		}

		else
			argv[argc] = buf;

		++argc;

		/* judge if '>' '>>' appear at the the time */
		if(res[3]&&res[4])
		{
			printf("`>' and '>>' are conflict\n");
			res[0]=1;
			return;
		}

		buf = delim + 1;

		while (*buf && (*buf == ' '))   /* ignore spaces */
			buf++;

		if (*buf == '\'') 
		{
		    buf++;
		    delim = strchr(buf, '\'');
		}

		else 
		{
		    delim = strchr(buf, ' ');
		}
    }

    
    /* the last is NULL */
    argv[argc] = NULL;
  

    /* ignore blank line */
    if (argc == 0)
    {
    	argv[0] = NULL;
    	res[0] = 1;
		return;
    }


    /* instrument can't end with '|' */
    if((line_index-1) && line[line_index-1] == argc-1)
    {
    	printf("you can't end up with '|'\n");
    	res[0]=1;
    	return;
    }

    /* '<' should always in the front of '|' */ 
    for(int j = 1; j < line_index; ++j)
    {
    	if(res[2] && line[j] < res[2])
    	{
    		printf("'<' should be in the head block\n");
    		res[0]=1;
    		return;
    	}
    }

    
    /* '>' should always in the back of '|' */
    for(int j = 1; j < line_index; ++j)
    {
    	if(res[3] && line[j] > res[3])
    	{
    		printf("'>' should be in the tail block\n");
    		res[0]=1;
    		return;
    	}
    }


    /* '>>' should always in the back of '|' */
    for(int j = 1; j < line_index; ++j)
    {
    	if(res[4] && line[j] > res[4])
    	{

    		printf("'>>' should be in the tail block\n");
    		res[0]=1;
    		return;
    	}
    }


    if(res[2] && res[2]==(argc-1))
    {
    	printf("you don't defined the file after '<'\n");
    	res[0] = 1;
    	return;
    }

    if(res[3] && res[3]==(argc-1))
    {
    	printf("you don't defined the file after '>'\n");
    	res[0] = 1;
    	return;
    }

    if(res[4] && res[4]==(argc-1))
    {
    	printf("you don't defined the file after '>>'\n");
    	res[0] = 1;
    	return;
    }

    /* should the job run in the background? */
    if (!strcmp(argv[argc-1], "&")) 
    {
		argv[--argc] = NULL;
		res[1]=1;
    }


    *pipe_num = line_index-1;
    printf("the argc is %d\n",argc);
    printf("the last block is : %s\n",argv[argc-1] );
    return;
}



/* 
 * builtin_cmd - If the user has typed a built-in command then execute
 *    it immediately.  
 */
int builtin_cmd(char **argv)
{
	if(!strcmp(argv[0],"cd"))
	{
		char path[MAXPATH];
		char currentPath[MAXPATH];

		if(!argv[1])
		{
			return 1;
			// strcpy(path,userPath);
		}

		else
			if(argv[1][0]=='~')      //if the path begins with ~, the origin function will view it as /home/wyz
			{
				strcpy(path,userPath);
				strcat(path,argv[1]+1);
			}

			else
			{
				if(argv[1][0]=='/')
					strcpy(path,argv[1]);
				else
				{
					getcwd(currentPath,MAXPATH);
					strcpy(path,currentPath);
					strcat(path,"/");
					strcat(path,argv[1]);
				}
			}

		chdir(path);
		getcwd(currentPath,MAXPATH);
		
		if(strcmp(path,currentPath)!=0)
			printf("No such a file or directory\n");

		else
		{
			strcpy(prompt,path);
			strcat(prompt," $");	
		}

		return 1;
	}

	if(!strcmp(argv[0],"jobs"))
    {
    	// listjobs(jobs);
    	return 1;
    }

	if(!strcmp(argv[0],"history"))
	{
		if(!argv[1])
			history1(jobs);
		
		else
			history2(jobs,atoi(argv[1]));

		return 1;
	}


    if (!strcmp(argv[0], "quit") || !strcmp(argv[0], "exit"))   /* Quit command */
    	exit(0);


	if(!strcmp(argv[0], "bg") || !strcmp(argv[0], "fg"))
	{
		do_bgfg(argv);
		return 1;
	}


    if (!strcmp(argv[0], "&"))    /* Ignore singleton & */
    	return 1;


    return 0;                     /* Not a builtin command */
}



/* 
 * do_bgfg - Execute the builtin bg and fg commands
 */
void do_bgfg(char **argv) 
{
	int pid = 0;
	const char * str_number;
	struct job_t * job;
	char *first_cmd = argv[0];
	char *second_cmd = argv[1];
	char e;

	const char *err_msg1 = "%s command requires a PID\n";
	const char *err_msg2 = "%s argument must be a PID\n";
	const char *err_msg3 = "[%d]: No such process\n";

	if(second_cmd == NULL)            //if there is no pid
    {
		printf(err_msg1, first_cmd);
		return;
    }


	else
	{
		for(long unsigned i = 0; i < strlen(second_cmd); i++)
		{
			e = second_cmd[i];

			if(e < '0' || e > '9')
			{
				printf(err_msg2, first_cmd);
				return;
			}
		}

		pid = atoi(second_cmd);
		job = getJobByPID(jobs, pid);

		if(!job)
		{
			printf(err_msg3, pid);
			return;
		}
    }
    
	kill(-pid, SIGCONT);           //whatever it is a "bg" or "fg", the job is going to run
	
	if(!strcmp(first_cmd, "bg"))    //bg
	{
		printf("this is bg\n");
		if(job->state != BG)
			--fg_job_num;

		job->state = BG;
		printf("[%d] %s", pid, job->cmdline);
	}

	else                            //fg
	{
		if(job->state != FG)
			++fg_job_num;
		

		job->state = FG;
		waitfg_1(job->pid);      
	}

 	return;
}



/* 
 * waitfg - Blodk until the foregroud process is finished
 */
void waitfg_1(pid_t pid)
{
	// waitpid(pid,NULL,WUNTRACED);
	while(fgPID(jobs)==pid)
	{
		sleep(0.5);
	}
	return;
}

void waitfg_2()
{
	int count=0;
	pid_t pid;
	while(pid=fgPID(jobs))
	{
		// printf("now the pid is:%d\n", pid);
		sleep(0.5);
/*		if(count==3)
		{
			count=0;
			kill(pid, SIGKILL);
		}
		++count;*/
	}

	// waitpid(-1,NULL,WUNTRACED);
	return;
}




/*****************
 * Signal handlers
 *****************/

/* 
 * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
 *     a child job terminates (becomes a zombie), or stops because it
 *     received a SIGSTOP or SIGTSTP signal. The handler reaps all
 *     available zombie children, but doesn't wait for any other
 *     currently running children to terminate.  
 */
void sigchld_handler(int sig)
{
	pid_t pid;
	int status;
	struct job_t *job;

	while((pid = waitpid(-1, &status, WUNTRACED|WNOHANG))>0)    /*to see which process is exited or stopped */
	{
		if(WIFEXITED(status))	      /* normal exit*/
		{
			if(!deleteJob(jobs,pid))
				app_error("can't delete the exited job");
			else
				--fg_job_num;

		}

		if(WIFSIGNALED(status))	      /* terminated by a signal */
		{
			if(!deleteJob(jobs,pid))
				app_error("can't delete the signaled job");

			else if(WTERMSIG(status)==2)
			{
				printf("Progress [%d] terminated by signal %d\n",pid, WTERMSIG(status));
				--fg_job_num;	
			}
		}

		if(WIFSTOPPED(status))	      /* stopped by a signal */
		{
			printf("Progress [%d] stopped by signal %d\n",pid, WSTOPSIG(status));
			job = getJobByPID(jobs, pid);
			job->state = ST;
			--fg_job_num;
		}
    }
}




/* 
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.  
 */
void sigint_handler(int sig)
{
	pid_t fpid;
	while(fg_job_num)
	{
		fpid = fgPID(jobs);
		if(fpid)
		{
			kill(-fpid, sig);
		}	
	}
	return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.  
 */
void sigtstp_handler(int sig) 
{
	pid_t fpid;
	while(fg_job_num)
	{
		fpid = fgPID(jobs);
		if(fpid)
		{
			kill(-fpid, sig);
		}
	}
	return;
}

/*********************
 * End signal handlers
 *********************/

/***********************************************
 * Helper routines that manipulate the job list*
 ***********************************************/

/* clearJob - Clear the entries in a job struct */
void clearJob(struct job_t *job) {
    job->pid = 0;
    job->state = UNDEF;
    job->cmdline[0] = '\0';
}

/* initJobs - Initialize the job list and the history*/
void initJobs() 
{
    for (int i = 0; i < MAXJOBS; i++)
		clearJob(&jobs[i]);

}

/* initHis */
void initHis()
{
	for (int i = 0; i < MAXJOBS; i++)
		his[i][0]='\0';
}


/* addJob - Add a job to the job list */
int addJob(struct job_t *jobs, pid_t pid, int state, char *cmdline) 
{
    
    if (pid < 1)
    {
    	printf("PID can't less than 1 when adding job\n");
		return 0;
    }

    for (int i = 0; i < MAXJOBS; ++i) 
    {
		if (jobs[i].pid == 0)      // find a vacant position
		{
		    jobs[i].pid = pid;
		    jobs[i].state = state;
		    strcpy(jobs[i].cmdline, cmdline);
		    
		    ++next_job_index;
		    return 1;
		}
    }

    printf("Tried to create too many jobs\n");
    return 0;
}


/* deleteJob - Delete a job whose PID=pid from the job list */
int deleteJob(struct job_t *jobs, pid_t pid) 
{
    if (pid == 0)
    {
    	printf("PID can't be 0 when deleting job\n");
		return 0;
    }

    for (int i = 0; i < MAXJOBS; i++) 
    {
		if (jobs[i].pid == pid)
		{
		    clearJob(&jobs[i]);
		    return 1;
		}
    }

    printf("this pid doesn't exists in user scope\n");
    return 0;
}


/* fgPID - Return PID of current foreground job, 0 if no such job */
pid_t fgPID(struct job_t *jobs)
{
    for (int i = 0; i < MAXJOBS; ++i)
	if (jobs[i].state == FG)
	    return jobs[i].pid;
    return 0;
}


/* getJobByPID  - Find a job (by PID) on the job list */
struct job_t * getJobByPID(struct job_t *jobs, pid_t pid)
{
    if (pid < 1)
		return NULL;
    for (int i = 0; i < MAXJOBS; i++)
		if (jobs[i].pid == pid)
	    	return &jobs[i];
    return NULL;
}



/* history - Print the history */
int history1(struct job_t *jobs)
{
	for (int i = 0; i < his_next_index; i++) 
    {
		printf("%d  %s", i+1,his[i]);
    }
	return 0;
}



int history2(struct job_t *jobs,int n)
{
	if(n >= his_next_index)
	{
		printf("You total instruments amount is %d\n", his_next_index-1);
		return 1;
	}

    for (int i = 0; i < n; i++) 
		printf("%d  %s", i+1, his[i]);

    return 0;
}
/******************************
 * end job list helper routines
 ******************************/


/***********************
 * Other helper routines
 ***********************/


/*
 * unix_error - unix-style error routine
 */
void unix_error(char *msg)
{
    fprintf(stdout, "%s: %s\n", msg, strerror(errno));
    exit(1);
}

/*
 * app_error - application-style error routine
 */
void app_error(char *msg)
{
    fprintf(stdout, "%s\n", msg);
    exit(1);
}



/*
 * Signal - wrapper for the sigaction function
 */
handler_t *Signal(int signum, handler_t *handler) 
{
    struct sigaction action, old_action;

    action.sa_handler = handler;  
    sigemptyset(&action.sa_mask); /* block sigs of type being handled */
    action.sa_flags = SA_RESTART; /* restart syscalls if possible */

    if (sigaction(signum, &action, &old_action) < 0)
		unix_error("Signal error");
    return (old_action.sa_handler);
}



/*
 * sigquit_handler - The driver program can gracefully terminate the
 *    child shell by sending it a SIGQUIT signal.
 */
void sigquit_handler(int sig) 
{
    printf("Terminating after receipt of SIGQUIT signal\n");
    exit(1);
}



